package mo.leetcode_hot;

public class L494 {

    private int count;

    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, 0, 0, target);
        return count;
    }

    private void backtrack(int[] nums, int idx, int sum, int target) {
        if (idx == nums.length) {
            if (sum == target) {
                count++;
            }
            return;
        }
        backtrack(nums, idx+1, sum+nums[idx], target);
        backtrack(nums, idx+1, sum-nums[idx], target);
    }

}
